shared source/sscli20/jscript/engine/simplehashtable.cs

   1 // ==++==
   2 //
   3 //
   4 //    Copyright (c) 2006 Microsoft Corporation.  All rights reserved.
   5 //
   6 //    The use and distribution terms for this software are contained in the file
   7 //    named license.txt, which can be found in the root of this distribution.
   8 //    By using this software in any fashion, you are agreeing to be bound by the
   9 //    terms of this license.
  10 //
  11 //    You must not remove this notice, or any other, from this software.
  12 //
  13 //
  14 // ==--==
  15
  16 namespace Microsoft.JScript {
  17
  18     using System;
  19     using System.Collections;
  20     using System.Globalization;
  21     using System.Reflection;
  22
  23     internal sealed class HashtableEntry{
  24       internal Object key;
  25       internal Object value;
  26       internal uint hashCode;
  27       internal HashtableEntry next;
  28
  29       internal HashtableEntry(Object key, Object value, uint hashCode, HashtableEntry next){
  30         this.key = key;
  31         this.value = value;
  32         this.hashCode = hashCode;
  33         this.next = next;
  34       }
  35     }
  36
  37     public sealed class SimpleHashtable{
  38       private HashtableEntry[] table;
  39       internal int count;
  40       private uint threshold;
  41
  42       public SimpleHashtable(uint threshold){
  43         if (threshold < 8)
  44           threshold = 8;
  45         this.table = new HashtableEntry[(int)(threshold * 2 - 1)];
  46         this.count = 0;
  47         this.threshold = threshold;
  48       }
  49
  50       public IDictionaryEnumerator GetEnumerator(){
  51         return new SimpleHashtableEnumerator(this.table);
  52       }
  53
  54       private HashtableEntry GetHashtableEntry(Object key, uint hashCode){
  55         int index = (int)(hashCode % (uint)this.table.Length);
  56         HashtableEntry e = this.table[index];
  57         if (e == null) return null;
  58         if (e.key == key) return e;
  59         HashtableEntry prev = e;
  60         HashtableEntry curr = e.next;
  61         while (curr != null){
  62           if (curr.key == key)
  63             return curr;
  64           prev = curr;
  65           curr = curr.next;
  66         }
  67         if (e.hashCode == hashCode && e.key.Equals(key)){
  68           e.key = key; return e;
  69         }
  70         prev = e;
  71         curr = e.next;
  72         while (curr != null){
  73           if (curr.hashCode == hashCode && curr.key.Equals(key)){
  74             curr.key = key; return curr;
  75           }
  76           prev = curr;
  77           curr = curr.next;
  78         }
  79         return null;
  80       }
  81
  82       internal Object IgnoreCaseGet(String name){
  83         for (uint i = 0, n = (uint)this.table.Length; i < n; i++){
  84           HashtableEntry e = this.table[i];
  85           while (e != null){
  86             if (String.Compare((String)e.key, name, StringComparison.OrdinalIgnoreCase) == 0) return e.value;
  87             e = e.next;
  88           }
  89         }
  90         return null;
  91       }
  92
  93       private void Rehash(){
  94         HashtableEntry[] oldTable = this.table;
  95         uint threshold = this.threshold = (uint)(oldTable.Length+1);
  96         uint newCapacity = threshold * 2 - 1;
  97         HashtableEntry[] newTable = this.table = new HashtableEntry[newCapacity];
  98         for (uint i = threshold-1; i-- > 0;){
  99           for (HashtableEntry old = oldTable[(int)i]; old != null; ){
 100             HashtableEntry e = old; old = old.next;
 101             int index = (int)(e.hashCode % newCapacity);
 102             e.next = newTable[index];
 103             newTable[index] = e;
 104           }
 105         }
 106       }
 107
 108       public void Remove(Object key){
 109         uint hashCode = (uint)key.GetHashCode();
 110         int index = (int)(hashCode % (uint)this.table.Length);
 111         HashtableEntry e = this.table[index];
 112         Debug.Assert(e != null);
 113         this.count--;
 114         while (e != null && e.hashCode == hashCode && (e.key == key || e.key.Equals(key)))
 115           e = e.next;
 116         this.table[index] = e;
 117         do{
 118           if (e == null) return;
 119           HashtableEntry f = e.next;
 120           while (f != null && f.hashCode == hashCode && (f.key == key || f.key.Equals(key)))
 121             f = f.next;
 122           e.next = f;
 123           e = f;
 124         }while(true);
 125       }
 126
 127       public Object this[Object key]{
 128         get{
 129           HashtableEntry e = this.GetHashtableEntry(key, (uint)key.GetHashCode());
 130           if (e == null) return null;
 131           return e.value;
 132         }
 133         set{
 134           uint hashCode = (uint)key.GetHashCode();
 135           HashtableEntry e = this.GetHashtableEntry(key, hashCode);
 136           if (e != null){
 137             e.value = value; return;
 138           }
 139           if (++this.count >= this.threshold) this.Rehash();
 140           int index = (int)(hashCode % (uint)this.table.Length);
 141           this.table[index] = new HashtableEntry(key, value, hashCode, this.table[index]);
 142         }
 143       }
 144
 145     }
 146
 147     internal sealed class SimpleHashtableEnumerator : IDictionaryEnumerator{
 148       private HashtableEntry[] table;
 149       private int count;
 150       private int index;
 151       private HashtableEntry currentEntry;
 152
 153       internal SimpleHashtableEnumerator(HashtableEntry[] table){
 154         this.table = table;
 155         this.count = table.Length;
 156         this.index = -1;
 157         this.currentEntry = null;
 158       }
 159
 160       public Object Current{ //Used by expando classes to enumerate all the keys in the hashtable
 161         get{
 162           return this.Key;
 163         }
 164       }
 165
 166       public DictionaryEntry Entry{
 167         get{
 168           return new DictionaryEntry(this.Key, this.Value);
 169         }
 170       }
 171
 172       public Object Key{
 173         get{
 174           return this.currentEntry.key;
 175         }
 176       }
 177
 178       public bool MoveNext(){
 179         HashtableEntry[] table = this.table;
 180         if (this.currentEntry != null){
 181           this.currentEntry = this.currentEntry.next;
 182           if (this.currentEntry != null)
 183             return true;
 184         }
 185         for (int i = ++this.index, n = this.count; i < n; i++)
 186           if (table[i] != null){
 187             this.index = i;
 188             this.currentEntry = table[i];
 189             return true;
 190           }
 191         return false;
 192       }
 193
 194       public void Reset(){
 195         this.index = -1;
 196         this.currentEntry = null;
 197       }
 198
 199       public Object Value{
 200         get{
 201           return this.currentEntry.value;
 202         }
 203       }
 204
 205     }
 206
 207 }
 208